[AGC041E] Balancing Network

### 题目描述 平衡网络是一个由 $M$ 个平衡器所连接的 $N$ 根导线所构成的抽象网络系统。这一系统按由左至右的顺序运行。导线从上到下按 $1$ 至 $N$ 编号，平衡器从左到右按 $1$ 至 $M$ 编号。第 $i$ 个平衡器连接着导线 $x_i$ 与 $y_i$。下图是一个平衡网络的示例：  每个平衡器都一定处于以下两种状态之一：向上或向下。 让我们考虑一个令牌，这个令牌在所有平衡器左侧的某个点开始沿某根导线向右移动。在此过程中，每个平衡器都会被令牌恰好**途经**一次。当令牌途经一个平衡器 $i$ 时，可能会发生以下情况： - 如果令牌沿导线 $x_i$ 移动且平衡器 $i$ 处于向下的状态，则令牌会向下移至 $y_i$ 并继续向右移动。 - 如果令牌沿导线 $y_i$ 移动且平衡器 $i$ 处于向上的状态，则令牌会向上移至 $x_i$ 并继续向右移动。 - 否则，令牌不会改变其移动的导线。 我们将所有平衡器的状态用长度为 $M$ 的字符串表示。若第 $i$ 个平衡器处于向上的状态，则第 $i$ 个字符为'`^`'；若第 $i$ 个平衡器处于向下的状态，则第 $i$ 个字符为'`v`'。 如果存在一根导线 $w$ ，使得令牌无论从整个网络的哪一根导线开始移动都能抵达导线 $w$ 且一直沿此导线移动至趋向无穷远的位置，那么这个网络称之为均匀状态；任何的其他状态称之为非均匀状态。 给出一个整数 $T (1 \le T \le 2)$ ，请您根据 $T$ 的值回答以下问题： - 若 $T=1$，则通过自行规定平衡器的方向以构造给出网络的任何均匀状态，或是回答不存在。 - 若 $T=2$，则通过自行规定平衡器的方向以构造给出网络的任何非均匀状态，或是回答不存在。 请注意，若您仅正确回答了一种问题，则您将获得一定的部分分。 ### 数据范围 - $2 \le N \le 50000$ - $1 \le M \le 10^5$ - $1 \le T \le 2$ - $1 \le x_i \lt y_i \le N $ - 保证所有输入均为整数。 ### 子任务 - 若您通过了所有 $T=1$ 时的所有测试点，则您将获得 $50 \%$ 的分数。（译注：原文是800分，但本题的实际分数为1600分，翻译时按照 $50 \%$ 翻译） - 若您通过了所有 $T=2$ 时的所有测试点，则您将获得 $50 \%$ 的分数。 ### 输入格式 输入将由以下的格式给出： ```input N M T x1 y1 x2 y2 : xM yM ```` ### 输出格式 请输出一个字符串，以表示所有平衡器的状态。 若 $T=1$ ，则输出给定网络的任何一种均匀状态。 若 $T=2$ ，则输出给定网络的任何一种非均匀状态。 若所需的状态不存在，则输出 `-1`。 ### 样例解释 #### 样例1 对于给定网络，下图的状态是均匀的：无论起始导线是什么，令牌都将在导线1处结束。  #### 样例2 对于给定网络，下图的状态是非均匀的：无论起始导线是什么，令牌都将在导线1处或导线2处结束。  #### 样例3 对于给定网络，不存在任何一种均匀状态。 #### 样例3 对于给定网络，不存在任何一种非均匀状态。

[problemUrl]: https://atcoder.jp/contests/agc041/tasks/agc041_e *平衡ネットワーク* とは、左から右へと延びる $ N $ 本のケーブルと、それぞれ $ 2 $ 本のケーブルを繋ぐ $ M $ 個の *平衡器* からなる抽象機械です。 ケーブルには上から順に $ 1 $ から $ N $ までの番号が、平衡器には左から順に $ 1 $ から $ M $ までの番号がついています。平衡器 $ i $ はケーブル $ x_i,\ y_i $ ($ x_i\ <\ y_i $) を繋ぎます。  各平衡器は *上* または *下* のいずれかの状態に設定します。 $ 1 $ 枚のコインが、いずれかのケーブルに沿ってどの平衡器よりも左に位置する点から右へと流れ始めるとします。 これから、このコインはすべての平衡器のもとをちょうど一度ずつ通過します。 コインが平衡器 $ i $ の位置に来たとき、次のことが起こります。 - コインがケーブル $ x_i $ に沿って流れており、かつ平衡器 $ i $ の状態が下であるなら、コインはケーブル $ y_i $ に移ってから再び右へと流れる。 - コインがケーブル $ y_i $ に沿って流れており、かつ平衡器 $ i $ の状態が上であるなら、コインはケーブル $ x_i $ に移ってから再び右へと流れる。 - 上記のいずれでもないなら、コインが別のケーブルに移ることはない。 平衡ネットワークの状態とは、すべての平衡器の状態を表す長さ $ M $ の文字列です。 この文字列の $ i $ 文字目は、平衡器 $ i $ の状態が上なら `^`、下なら `v` です。 平衡ネットワークの状態が *均一的* であるとは、あるケーブル $ w $ が存在して、コインがどのケーブルから流れ始めたとしてもケーブル $ w $ に行き着き、これに沿って永遠に流れることをいいます。それ以外の場合、平衡ネットワークの状態は *非均一的* であるといわれます。 整数 $ T $ ($ 1\ \le\ T\ \le\ 2 $) が与えられます。次の問いに答えてください。 - $ T\ =\ 1 $ の場合は、このネットワークの均一的な状態をいずれかひとつ求めるか、そのような状態が存在しないことを検出せよ。 - $ T\ =\ 2 $ の場合は、このネットワークの非均一的な状態をいずれかひとつ求めるか、そのような状態が存在しないことを検出せよ。 なお、いずれか $ 1 $ 種類の問いにのみ正しく答えると部分点が得られます。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ M $ $ T $ $ x_1 $ $ y_1 $ $ x_2 $ $ y_2 $ $ : $ $ x_M $ $ y_M $

$ T\ =\ 1 $ の場合は与えられたネットワークの均一的な状態をいずれかひとつ出力し、$ T\ =\ 2 $ の場合は非均一的な状態をいずれかひとつ出力せよ。ただし、そのような状態が存在しないなら `-1` と出力せよ。

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

^^^^^

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

v^^^^

3 1 1
1 2

-1

2 1 2
1 2

-1

### 制約 - $ 2\ \leq\ N\ \leq\ 50000 $ - $ 1\ \leq\ M\ \leq\ 100000 $ - $ 1\ \leq\ T\ \leq\ 2 $ - $ 1\ \leq\ x_i\ <\ y_i\ \leq\ N $ - 入力中のすべての値は整数である。 ### 部分点 - $ T\ =\ 1 $ であるようなテストケースすべてに正解すると、$ 800 $ 点が与えられる。 - $ T\ =\ 2 $ であるようなテストケースすべてに正解すると、$ 800 $ 点が与えられる。 ### Sample Explanation 1 どのケーブルから流れ始めてもコインはケーブル $ 1 $ に行き着くため、この状態は均一的です。 !\[pic2-small-2acea94b.png\](https://img.atcoder.jp/agc041/pic2-small-2acea94b.png) ### Sample Explanation 2 流れ始めるケーブル次第で、コインはケーブル $ 1 $ にもケーブル $ 2 $ にも行き着くことがあるため、この状態は非均一的です。 !\[pic3final-small-2acea94b.png\](https://img.atcoder.jp/agc041/pic3final-small-2acea94b.png) ### Sample Explanation 3 均一的な状態が存在しません。 ### Sample Explanation 4 非均一的な状態が存在しません。