QSTABLE - Queen and Stable Relationships

no tags 

Swayamvara, in ancient India, was a practice of choosing a husband, from a list of suitors by a girl of marriageable age.

It is the swayamvara of gossip queen of IIIT, Akshata. Now, Akshata is always interested in knowing the stability of the relationships among various students of IIIT. Nowadays she is very busy in her swayamvara’s preparation and is not able to update herself about the latest gossips. As you know she is the gossip queen. She would love if someone could do her a favor and collect answers of her questions about relationships in IIIT. It might increase the collector’s chance of getting selected for marriage.

Before starting preparations for the swayamvara, Akshata used to maintain notes about the relationships in IIIT and knew all about them. So she thought she can help you by providing the notes.

There are various ways in which two people can be acquaintances :

  1. If A and B are in a relationship, then A and B are acquaintances of each other.
  2. If A and B are acquaintances of each other and B and C are acquaintances of each other, then A and C are also acquaintances of each other.

In Akshata's notes, a relationship between person1 and person2 is represented as "person1 person2". The Queen's questions are also special.

There are two types of questions:

  1. First type of query is whether two people, say A and B, still remain each others’ acquaintances even if two people, say C and D, break-up and end their relationship.
  2. Second type of query is whether two people, say A and B, still remain acquaintances even if a person, say C, leaves the college (It’s obvious that before leaving college, C ends all his/her relationships).


Input Format:

First line of the input contains two integers, N and M where N represents the number of people in IIIT and M represents the number of relationships in Akshata’s notes.

The next M lines contain 2 strings each, containing the names of 2 people who are in a relationship.

Next line contains a single integer Q, which represents the number of questions asked by the Queen. Each of the next Q lines represents a query. For every query first integer represents the query type.

If the query type is 1 then it is followed by four strings in the same line, representing A B C and D. you have to output "STABLE" if A and B remain acquaintance of each other even if C and D break up and "NOT STABLE" otherwise.

If the query type is 2 then it is followed by three strings in the same line, representing A B and C. You have to output "STABLE" if A and B remain acquaintances even if C leaves college otherwise output "NOT STABLE". (All quotes for clarity)

Output Format:

For every query output "STABLE" or "NOT STABLE" without quotes.

Constraints:

1 ≤ N ≤ 10000
1 ≤ M ≤ 50000
1 ≤ Q ≤ 10000
Size of all strings will be less than 50 characters.

Sample Input:

3 2
Person1 Person2
Person1 Person3
2
2 Person2 Person3 Person1
1 Person1 Person2 Person1 Person3

Sample Output:

NOT STABLE
STABLE

Explanation:

Person1 is in a relationship with Person2 and Person1 is also in a relation with Person3. So Person3 and Person2 are acquaintance.
First Query:
But Person2 and Person3 are acquaintance of each other only because of person1, if person1 leaves the college, then Person2 and Person3 are also not acquaintance of each other.
Second Query:
Person1 will remain being acquaintance of Person2 even if Person1 breaks-up with Person3.

Sample Input:

17 18
Person1 Person2
Person1 Person4
Person2 Person4
Person4 Person6
Person2 Person6
Person2 Person3
Person3 Person5
Person1 Person7
Person7 Person8
Person7 Person9
Person7 Person10
Person9 Person12
Person8 Person12
Person8 Person11
Person12 Person13
Person14 Person15
Person15 Person16
Person16 Person17
8
2 Person1 Person14 Person7
2 Person1 Person2 Person2
1 Person1 Person14 Person2 Person4
1 Person5 Person13 Person1 Person2
1 Person6 Person2 Person1 Person4
1 Person13 Person6 Person7 Person8
2 Person13 Person6 Person7
2 Person13 Person6 Person8
2 Person13 Person8 Person7

Sample Output:

NOT STABLE
NOT STABLE
NOT STABLE
STABLE
STABLE
STABLE
NOT STABLE
STABLE


Problem Setter: Mayank Natani


hide comments
Oleg: 2023-10-26 07:25:42

weird constraints... naive O(M*Q) solution passes.

Jose Sanchez: 2014-02-16 21:38:07

Hello, can you tell me what is the problem with my solution? I made a test cases generator and all were okey :/.


Added by:darkshadows
Date:2014-01-28
Time limit:1s-2s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64