rhezo-and-destructive-mind

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 ≤ N, M, Q ≤ 10^{2} 

1 ≤ A_i, B_i ≤ N

1 ≤ X ≤ N

SAMPLE INPUT
5 5
1 2
2 3
3 4
4 5
3 5
5
1
2
3
4
5

SAMPLE OUTPUT
Not Satisfied
Satisfied 2
Satisfied 3
Not Satisfied
Not Satisfied

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.

Source: hackerearth | Difficulty: EASY
Tags: Graph algorithms

Graph traversal


Solutions: