seuOJ541 - 心意无向，前程有向

题目描述

给你一张由有向边和无向边组成的图。要求你确定所有无向边的方向，转为有向边。使得图中没有环。若无解输出 −1-1 。

输入格式

第一行两个正整数 n,m1,m2(1≤n,m1,m2≤2×105)n,m_1,m_2(1\le n,m_1,m_2 \le 2\times 10^5)，分别代表图中的顶点数，无向边的边数和有向边的边数。

后 m1m_1 行，第 ii 行两个正整数 ui,vi(1≤ui,vi≤n;ui≠vi)u_i,v_i(1\le u_i,v_i\le n;u_i\neq v_i) 表示存在一条连接 uiu_i 和 viv_i 的无向边。

后 m2m_2 行，第 ii 行两个正整数 xi,yi(1≤xi,yi≤n;xi≠yi)x_i,y_i(1\le x_i,y_i\le n;x_i\neq y_i) 表示存在一条从xix_i 到 yiy_i 的有向边。

保证图中不存在重边或自环。

输出格式

无解：输出 −1-1 。

有解：输出 m1m_1 行，每行两个正整数 ui′,vi′u_i',v_i' 表示第 ii 条无向边被定向为了 ui′u_i' 到 vi′v_i' 的有向边。

若有多组解，你只需输出任意一种即可。

样例

输入样例

6 3 5
4 5
3 5
2 3
1 2
1 3
2 4
2 5
1 5

输出样例

5 4
3 5
3 2

输入样例

6 3 5
4 5
3 5
2 3
1 2
1 3
2 4
2 5
5 1

输出样例

-1