[Solution] Neighbour Ordering solution codeforces

Neighbour Ordering solution codeforces – Given an undirected graph 𝐺G, we say that a neighbour ordering is an ordered list of all the neighbours of a vertex for each of the vertices of 𝐺G. Consider a given neighbour ordering of 𝐺G and three vertices 𝑢u𝑣v and 𝑤w, such that 𝑣v is a neighbor of 𝑢u and 𝑤w. We write 𝑢<𝑣𝑤u<vw if 𝑢u comes after 𝑤w in 𝑣v‘s neighbor list.

Neighbour Ordering solution codeforces

A neighbour ordering is said to be good if, for each cycle 𝑣1,𝑣2,,𝑣𝑐v1,v2,…,vc of the graph, one of the following is satisfied:

  • 𝑣1<𝑣2𝑣3,𝑣2<𝑣3𝑣4,,𝑣𝑐2<𝑣𝑐1𝑣𝑐,𝑣𝑐1<𝑣𝑐𝑣1,𝑣𝑐<𝑣1𝑣2v1<v2v3,v2<v3v4,…,vc−2<vc−1vc,vc−1<vcv1,vc<v1v2.
  • 𝑣1>𝑣2𝑣3,𝑣2>𝑣3𝑣4,,𝑣𝑐2>𝑣𝑐1𝑣𝑐,𝑣𝑐1>𝑣𝑐𝑣1,𝑣𝑐>𝑣1𝑣2v1>v2v3,v2>v3v4,…,vc−2>vc−1vc,vc−1>vcv1,vc>v1v2.

Given a graph 𝐺G, determine whether there exists a good neighbour ordering for it and construct one if it does.

Input

The input consists of multiple test cases. The first line contains a single integer 𝑡t (1𝑡1041≤t≤104) — the number of test cases. Description of the test cases follows.

The first line of each test case contains two integers 𝑛n and 𝑚m (2𝑛31052≤n≤3⋅1051𝑚31051≤m≤3⋅105), the number of vertices and the number of edges of the graph.

The next 𝑚m lines each contain two integers 𝑢,𝑣u,v (0𝑢,𝑣<𝑛0≤u,v<n), denoting that there is an edge connecting vertices 𝑢u and 𝑣v. It is guaranteed that the graph is connected and there are no loops or multiple edges between the same vertices.

The sum of 𝑛n and the sum of 𝑚m for all test cases are at most 31053⋅105.

Neighbour Ordering solution codeforces

For each test case, output one line with YES if there is a good neighbour ordering, otherwise output one line with NO. You can print each letter in any case (upper or lower).

If the answer is YES, additionally output 𝑛n lines describing a good neighbour ordering. In the 𝑖i-th line, output the neighbours of vertex 𝑖i in order.

If there are multiple good neigbour orderings, print any.

Example
input

Copy
3
5 6
0 1
0 2
1 2
2 3
3 4
4 1
2 1
0 1
6 10
0 1
2 0
0 3
0 4
1 2
1 4
2 3
2 5
3 5
4 5

Neighbour Ordering solution codeforces

output

Copy
YES
1 2 
4 2 0 
0 1 3 
2 4 
3 1 
YES
1 
0 
NO

For Solution

Click Here

Leave a Comment