Welcome to the Grand Banquet Dilemma! Picture a gathering of folks connected by a web of relationships. This web of relationships is given as a connected tree with \(N\) vertices depicting people and \(N-1\) edges representing relationships (for each edge the corresponding two people know each other).
You're on a mission to throw an unforgettable party, but there's a twist – you've got two banquets, and you want to ensure that no two people who know each other end up in the same banquet.
Now, your task involves answering \(Q\) queries, each presenting a potential new relationship between two individuals, \(X\) and \(Y\). The burning question: If this new connection happens, can you still invite everyone to the party using the two banquets? If the answer is "\(No\)", you must figure out the minimum number of relationships to remove so that everyone gets an invite and the number of ways to do so.
NOTE: the queries are independent of each other. Adding a new relationship doesn't permanently change the relationship web.
Input format
- The first line contains a single integer \(T\), which denotes the number of test cases.
- For each test case:
- The first line contains \(N\) denoting the number of people.
- The following \(N-1\) lines contain 2 space-separated integers, \(u\) & \(v\) indicating that there is a relationship between person person \(u\) & person \(v\)
- The next line contains \(Q\) denoting the number of queries.
- The next \(Q\) lines contain 2 unique space-separated integers, \(X\) and \(Y\). It's guaranteed that \(X\) and \(Y\) initially don't have a relationship.
Output format
For each test case, answer all the \(Q\) queries. For each query print \(\text{Yes}\) if it's possible to invite everyone to the party using the 2 banquets, after adding the current query's relationship to the initial existing \(N-1\) relations, ensuring that no two people who know each other end up in the same banquet, otherwise print \(No\). If the answer is \(No\), in the next line, print 2 integers, the minimum number of relationships to remove so that everyone gets an invite, and the number of ways to do so.
Constraints
1 5 1 2 1 3 3 4 3 5 2 2 4 1 5
Yes No 1 3
The first line denotes T = 1.
For test case \(1\):
We are given:
- N = 5
- We need to answer 2 queries.
Now,
- For the first query, we add a relationship between persons 2 and 4. We can invite everyone by asking persons 1, 4 & 5 to join Banquet 1 and persons 2 & 3 to join Banquet 2, thus ensuring that no two people who know each other end up in the same banquet.
- Hence, the answer to the first query is \(Yes\).
- For the Second query, we add a relationship between persons 1 and 5, and it can be proved that after adding this relationship, we can not invite everyone such that no two people who know each other end up at the same banquet. But,
- If we remove the relationship existing between persons 1 and 3, we can invite everyone by asking persons 1 & 3 to join Banquet 1 and persons 2, 5 & 4 to join Banquet 2.
- Similarly, If we remove the relationship existing between persons 3 and 5, we can invite everyone by asking persons 1 & 4 to join Banquet 1 and persons 2, 5 & 3 to join Banquet 2.
- Similarly, If we remove the relationship existing between persons 1 and 5, we can invite everyone by asking persons 2 & 3 to join Banquet 1 and persons 1, 5 & 4 to join Banquet 2.
- Hence, the minimum number of relationships to remove so that everyone gets an invite is 1, and the number of ways to do so is 3.
-
Hence, the answer to the Second query is \(No\), followed by 2 integers in the next line as \(1\) & \(3\)
Please login to use the editor
You need to be logged in to access the code editor
Loading...
Please wait while we load the editor
Login to unlock the editorial
Please login to use the editor
You need to be logged in to access the code editor
Loading...
Please wait while we load the editor