#2637. flare
flare
题目背景
这是一个很有趣的想法,如果熊是蜜蜂,
他们会将他们的巢建在树下。
而且如此的话(如果蜜蜂是熊),
我们就不用爬上楼梯了。
题目描述
这是小熊维尼的一首充满抱怨的歌。你是否曾经想过,有些关于无向图的问题,如果把边看成点,点看成边,会更容易解决?这道题目正与此有关。
假设有一张无向图 ,让我们对 执行一次简单变换,来得到无向图 。 满足,每个 的顶点和 的一条边一一对应。 的一对顶点间有一条边,当且仅当在 中的对应边有一个公共顶点。
可能与你猜测的不一样,本题给出了 ,求一个满足条件的 。
输入格式
输入的第一行含两个数 ,代表点数和边数。接下来 行,每行有两个数 ,,表示 , 间有一条边。保证每条边连接了两个不同的顶点,每对顶点最多有一条边相连。
输出格式
如果这样的 不存在,输出 -1
。否则,输出 行,每行两个数,代表 的一条边的两个顶点。 的第 条边对应于 的顶点 。输出需要满足,每条边连接了不同的顶点,每对顶点间至多只有一条边。你可以自行给顶点标号,但顶点的标号需要是正整数,而且不应超过 。
3 3
1 2
1 3
2 3
1 2
1 3
2 3
提示
样例的图是“三角形”( 三个点,两两间均有边 )。容易看到“三角形”简单变换后仍是“三 角形”。当然,样例的解并不唯一。
数据规模与约定
对 的数据,。
对 的数据,。
对 的数据,。
对 的数据,。
对 的数据,。
对 的数据,,。