Preparando MOJI
One day Petya got a birthday present from his mom: a book called "The Legends and Myths of Graph Theory". From this book Petya learned about a hydra graph.
A non-oriented graph is a hydra, if it has a structure, shown on the figure below. Namely, there are two nodes u and v connected by an edge, they are the hydra's chest and stomach, correspondingly. The chest is connected with h nodes, which are the hydra's heads. The stomach is connected with t nodes, which are the hydra's tails. Note that the hydra is a tree, consisting of h + t + 2 nodes.
Also, Petya's got a non-directed graph G, consisting of n nodes and m edges. Petya got this graph as a last year birthday present from his mom. Graph G contains no self-loops or multiple edges.
Now Petya wants to find a hydra in graph G. Or else, to make sure that the graph doesn't have a hydra.
The first line contains four integers n, m, h, t (1 ≤ n, m ≤ 105, 1 ≤ h, t ≤ 100) — the number of nodes and edges in graph G, and the number of a hydra's heads and tails.
Next m lines contain the description of the edges of graph G. The i-th of these lines contains two integers ai and bi (1 ≤ ai, bi ≤ n, a ≠ b) — the numbers of the nodes, connected by the i-th edge.
It is guaranteed that graph G contains no self-loops and multiple edges. Consider the nodes of graph G numbered with integers from 1 to n.
If graph G has no hydra, print "NO" (without the quotes).
Otherwise, in the first line print "YES" (without the quotes). In the second line print two integers — the numbers of nodes u and v. In the third line print h numbers — the numbers of the nodes that are the heads. In the fourth line print t numbers — the numbers of the nodes that are the tails. All printed numbers should be distinct.
If there are multiple possible answers, you are allowed to print any of them.
9 12 2 3
1 2
2 3
1 3
1 4
2 5
4 5
4 6
6 5
6 7
7 5
8 7
9 1
YES
4 1
5 6
9 3 2
7 10 3 3
1 2
2 3
1 3
1 4
2 5
4 5
4 6
6 5
6 7
7 5
NO
The first sample is depicted on the picture below:
Informação
Provedor Codeforces
Código CF243B
Tags
Submetido 0
BOUA! 0
Taxa de BOUA's 0%
Datas 09/05/2023 08:40:28
Relacionados