201113: [AtCoder]ARC111 D - Orientation

Memory Limit:1024 MB Time Limit:2 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

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.

Input

题意翻译

- 给你一个 $N$ 个点,无重边,无自环,有 $M$ 条边的无向图,并且给你一个长度为 $N$ 的序列 $c_1,c_2,...,c_N$。 - 你需要给图中每一条无向边定向,使定向之后的有向图点 $i$ 能到达 $c_i$ 个点。注意此处要将点 $i$ 自己算入 $c_i$ 个点中。 - 数据保证有解,如果有多组解,输出任意一组即可。

加入题单

上一题 下一题 算法标签: