/ 
実行時間制限: 2 sec / メモリ制限: 1024 MB
配点 : 600 点
問題文
N 頂点 M 辺の単純な無向グラフが与えられます。頂点には 1, \cdots, N の番号がついています。i 番目の辺は頂点 a_i, b_i を繋いでいます。 また、正整数列 c_1, c_2, \cdots, c_N も与えられます。
このグラフを、次の条件を満たすように有向グラフに変換してください。つまり、各 i について無向辺 (a_i, b_i) を削除し、有向辺 a_i \to b_i、b_i \to a_i のどちらか 1 つを張ってください。
- 全ての i = 1, 2, \cdots, N について、頂点 i から(有向辺を好きな回数使うことで)到達可能な頂点数がちょうど c_i 個。なお、頂点 i 自身も 1 個と数える。
なお、この問題では、解が存在するような入力のみが与えられます。
制約
- 1 \leq N \leq 100
- 0 \leq M \leq \frac{N(N - 1)}{2}
- 1 \leq a_i, b_i \leq N
- 与えられるグラフに自己ループや多重辺は存在しない
- 1 \leq c_i \leq N
- 必ず題意を満たす解が存在する
入力
入力は以下の形式で標準入力から与えられる。
N M a_1 b_1 : a_M b_M c_1 c_2 ... c_N
出力
M 行出力せよ。
i 行目には、i 番目の辺について a_i \to b_i に辺を張りたい場合 ->、a_i \gets b_i に辺を張りたい場合 <- を出力せよ。
解が複数存在する場合、どれを出力しても構わない。
入力例 1
3 3 1 2 2 3 3 1 3 3 3
出力例 1
-> -> ->
長さ 3 のサイクルでは、どの頂点からも全ての頂点に到達できます。
入力例 2
3 2 1 2 2 3 1 2 3
出力例 2
<- <-
入力例 3
6 3 1 2 4 3 5 6 1 2 1 2 2 1
出力例 3
<- -> ->
グラフは非連結のこともあります。
Score : 600 points
Problem Statement
Given is a simple undirected graph with N vertices and M edges. The vertices are numbered 1, \cdots, N, and the i-th edge connects Vertices a_i and b_i. Also given is a sequence of positive integers: c_1, c_2, \cdots, c_N.
Convert this graph into a directed graph that satisfies the condition below, that is, for each i, delete the undirected edge (a_i, b_i) and add one of the two direted edges a_i \to b_i and b_i \to a_i.
- For every i = 1, 2, \cdots, N, there are exactly c_i vertices reachable from Vertex i (by traversing some number of directed edges), including Vertex i itself.
In this problem, it is guaranteed that the given input always has a solution.
Constraints
- 1 \leq N \leq 100
- 0 \leq M \leq \frac{N(N - 1)}{2}
- 1 \leq a_i, b_i \leq N
- The given graph has no self-loops and no multi-edges.
- 1 \leq c_i \leq N
- There always exists a valid solution.
Input
Input is given from Standard Input in the following format:
N M a_1 b_1 : a_M b_M c_1 c_2 ... c_N
Output
Print M lines.
To add the edge a_i \to b_i for the i-th edge, print -> in the i-th line; to add the edge b_i \to a_i for the i-th edge, print <-.
If there are multiple solutions, any of them will be accepted.
Sample Input 1
3 3 1 2 2 3 3 1 3 3 3
Sample Output 1
-> -> ->
In a cycle of length 3, you can reach every vertex from any vertex.
Sample Input 2
3 2 1 2 2 3 1 2 3
Sample Output 2
<- <-
Sample Input 3
6 3 1 2 4 3 5 6 1 2 1 2 2 1
Sample Output 3
<- -> ->
The graph may be disconnected.