P2017 [USACO09DEC] Dizzy Cows G

奶牛们在农场里互相比赛跑圈，但它们在绕圈跑时会变得非常头晕，而众所周知，头晕的奶牛是不会产奶的。农夫约翰想要将农场中所有的双向奶牛路径改为单向路径，以消除任何「环」并防止奶牛头晕。「环」使得奶牛可以通过一条或多条奶牛路径回到起点，从而完成一个循环或圈。 农场由 $N$ 个牧场组成（$1 \leq N \leq 100,000$），这些牧场被方便地编号为 $1$ 到 $N$。$M_1$ 条单向奶牛路径（$1 \leq M_1 \leq 100,000$）和 $M_2$ 条双向奶牛路径（$1 \leq M_2 \leq 100,000$）连接着这些牧场。没有路径直接连接一个牧场到自身，尽管可能有多条路径连接两个不同的牧场。奶牛可能可以或不可以通过一系列奶牛路径在任意两个给定的牧场之间旅行。 你的任务是为双向奶牛路径分配一个方向，使得整个农场（最终只有单向路径）没有环。也就是说，不应该有任何单向奶牛路径序列能回到其起始位置。现有的单向奶牛路径不形成环，应该保持原样。 单向奶牛路径从牧场 $A_i$（$1 \leq A_i \leq N$）到牧场 $B_i$（$1 \leq B_i \leq N$）。双向奶牛路径连接牧场 $X_i$（$1 \leq X_i \leq N$）和 $Y_i$（$1 \leq Y_i \leq N$）。 考虑这个例子： ```cpp 1-->2 | /| | / | |/ | 32 | /| | / | vL v 3

第一行三个整数 $n,m_1,m_2$，分别表示点数、有向边的数量、无向边的数量。 第二行起输入 $m_1$ 行，每行 $2$ 个整数 $a,b$，表示 $a$ 到 $b$ 有一条有向边。 接下来输入 $m_2$ 行，每行 $2$ 个整数 $a,b$，表示 $a$ 和 $b$ 之间有一条无向边。

对于每条无向边，我们要求按输入顺序输出你定向的结果，也就是说如果你输出 $a\ b$，那表示你将 $a$ 和 $b$ 之间的无向边定向为 $a \to b$。 注意，也许存在很多可行的解。你只要输出其中任意一个就好。

（由 ChatGPT 4o 翻译）