Queen and Stable Relationships
All submissions for this problem are available.
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 :
- If A and B are in a relationship, then A and B are acquaintances of each
- 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:
- 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
- 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).
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
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"
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)
For every query output "STABLE" or "NOT STABLE" without quotes.
1 ≤ N ≤ 10000
1 ≤ M ≤ 50000
1 ≤ Q ≤ 10000
Size of all strings will be less than 50 characters.
3 2 Person1 Person2 Person1 Person3 2 2 Person2 Person3 Person1 1 Person1 Person2 Person1 Person3
NOT STABLE STABLE
Person1 is in a relationship with Person2 and Person1 is also in a relation
with Person3. So Person3 and Person2 are acquaintance.
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.
Person1 will remain being acquaintance of Person2 even if Person1 breaks-up
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
NOT STABLE NOT STABLE NOT STABLE STABLE STABLE STABLE NOT STABLE STABLE
Problem Setter: Mayank Natani
|Time Limit:||2 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.5, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, CLOJ, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.