AT_agc041_e.[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$，则通过自行规定平衡器的方向以构造给出网络的任何非均匀状态，或是回答不存在。

请注意，若您仅正确回答了一种问题，则您将获得一定的部分分。

输入将由以下的格式给出：

N M T
x1 y1
x2 y2
:
xM yM

请输出一个字符串，以表示所有平衡器的状态。
若 $T=1$ ，则输出给定网络的任何一种均匀状态。
若 $T=2$ ，则输出给定网络的任何一种非均匀状态。
若所需的状态不存在，则输出 -1。

样例解释

样例1

对于给定网络，下图的状态是均匀的：无论起始导线是什么，令牌都将在导线1处结束。

样例2

对于给定网络，下图的状态是非均匀的：无论起始导线是什么，令牌都将在导线1处或导线2处结束。

样例3

对于给定网络，不存在任何一种均匀状态。

样例3

对于给定网络，不存在任何一种非均匀状态。

• $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 \%$ 的分数。