Rhezo and Destructive Mind

4

22 votes
Approved, Depth First Search, Easy, Graphs
Problem

Rhezo has bought a graph with N nodes and M edges. He has a destructive mind and often deletes some nodes(and of course its edges to other nodes of the graph).

He will ask you Q queries. Each query is denoted by an integer X, meaning that he will delete the node X. Since he has a destructive mind, he gets satisfied if the the new graph with deleted node has more number of connected components than the original graph.

If satisfied, he wants you to print "Satisfied"(without quotes) and the number of edges that were removed when deleting node X, else print "Not Satisfied"(without quotes). All queries are different, and the original graph is restored after each query.

Input:

First line contains N and M as described in the problem statement. Each of the next M lines contain 2 integers \(A_i\) and \(B_i\), meaning that there is an edge between node A and node B. Next line contains a single integer Q, denoting the number of queries. Each of the next Q lines contain a single integer X as described in the problem statement.

Output:

For each of the Q queries, if Rhezo is satisfied(that is the number of connected components of the new graph has increased), print "Satisfied"(without quotes), and the number of edges that will be deleted after a space. Else print "Not Satisfied".

Constraints:

\(1 \le N, M, Q \le 10^{2} \)

\(1 \le A_i, B_i \le N\)

\(1 \le X \le N\)

Time Limit: 1
Memory Limit: 256
Source Limit:
Explanation

For the second query, if we remove node 2, the graph disconnects and 2 connected components are formed. One having only {1} and other having {3,4,5}. Clearly, the number of edges removed are 2.

Editor Image

?