rhezo-and-hackerearth-3

Rhezo has just joined HackerEarth as an intern. Like most companies, HackerEarth too has a lot of computers and some departments. For efficient communication, it is very important that every computer can connect with each other in the same department, with the connection not being necessarily direct. 

When each computer can connect with any other computer in the same department, that department is said to be happy. Initially all departments are happy.

Rhezo's friend Lonewolf wants to have some fun, and will cut some connection between any two computers for Q days. You being the Happy Manager of HackerEarth, need to tell for each of the Q days, if some department becomes unhappy.

Input:

First line contains 2 integers N and M, denoting the number of computers and number of wire connections at HackerEarth. Each of the next M lines contain 2 integers A_i and B_i, meaning that computer number A_i is connected to computer number B_i. 

Next line contains an integer Q, denoting the number of days Lonewolf cuts a connection between 2 computers at HackerEarth. Each of the next Q lines contain a single integer P, which means that connection between computer A_p and computer B_p is cut.

Output:

For each of the Q days, you need to tell whether any department is unhappy or not. If all departments are happy, print "Happy"(without quotes), else print "Unhappy"(without quotes).

Constraints:

1 ≤ N ,M ≤ 10^{5} 

1 ≤ A_i, B_i ≤ N

1 ≤ P ≤ M

1 ≤ M ≤ max(10^{5},N \cdot (N-1) / 2)

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

SAMPLE OUTPUT
Unhappy
Unhappy
Happy
Happy
Happy

Explanation

For the 3^{rd} query, when we delete the connection between computer 3 and computer 4, these two computers can still connect via this connection : 3 \rightarrow 5 \rightarrow 4.

Source: hackerearth | Difficulty: EASY
Tags: Graph algorithms

Graph traversal


Solutions: