P2017 [USACO09DEC] Dizzy Cows G

题目描述

给出一个有 $n$ 个点、$m_1$ 条单向边、$m_2$ 条双向边的混合图。

你的任务：给所有的双向边指定一个方向，使得图中不存在环。

注：保证原图没有环。

输入格式

第一行三个整数 $n,m_1,m_2(1 \le n,m_1,m_2 \le 10^5)$。

下来 $m_1$ 行，每行 $2$ 个整数 $a,b(a \ne b)$，表示 $a$ 到 $b$ 有一条有向边。

下来 $m_2$ 行，每行 $2$ 个整数 $a,b(a \ne b)$，表示 $a$ 和 $b$ 中间有一条无向边。

输出格式

对于每条无向边，按输入顺序输出定向的结果，也就是如果输出 $a\ b$，那表示将 $a$ 和 $b$ 中间的无向边定向为 $a \to b$。

注意，也许存在很多可行的解，只要输出其中任意一个就好。

输入

4 2 3
1 2
4 3
1 3
4 2
3 2

输出

1 3
4 2
2 3