[Wannafly冬令营2018Day5]Cactus Draw(困难版)

内存限制：256 MB 时间限制：1000 ms

你有一棵仙人掌，你想把它画在平面上，使得没有边相交。

如果一个无向连通图的任意一条边最多属于一个简单环，我们就称之为仙人掌。所谓简单环即不经过重复的结点的环。

第一行两个整数 $n, m (1\leq n\leq 1000, 1\leq m \leq 2000)$，表示点数和边数。

接下来 $m$ 行，每行两个正整数 $u, v (1\leq u, v\leq n, u\neq v)$，保证不存在重边。

输出 $n$ 行，每行两个整数 $x_i, y_i (1\leq x_i, y_i\leq n)$，表示将第 $i$ 个点画到 $(x_i, y_i)$ 的位置，要求图中的每对边如果有公共点，那么只能在端点相交，否则不能相交。

如果有多组解，那么输出任意的解即可。

1 1
2 3
2 2

C1677 [Wannafly冬令营2018Day5]Cactus Draw(困难版)