All Tracks Data Structures Disjoint Data Structures Basics of Disjoint Data Structures Problem

What's wrong with this CYPHER guys?
Tag(s):

Dijkstra, Medium-Hard

Problem
Editorial
Analytics

CYPHER is well know for setting hard problems for the contest. During Code Apocalypse many teams were not able to solve single problem. So we decided to do something different for the next contest. We will allow teams to work together but only we can decide which teams will work together. If we say Team A can work with Team B and Team B can work with Team C then it means that Team A can also work with Team C and vice-versa.

Now we repeatedly announce two type of announcements.

First: J X Y which means Team X can work with Team Y.

Second: ? X Y were you have to find if Team X and Team Y can work together.

For every Second type of announcement you will tell yes if the team can work together and no if the teams cannot work together.

Output the total number of yes and number of no.

CONSTRAINT:

1<= t<= 10

1<=n<=10^5

1<=q<=10^5

INPUT:

First line contains an integer t denoting the number of test cases.

First line of each test case contains two integers n and q where n is the number of teams and q is the number of queries.

OUTPUT

For every second type of query print the total numbers of yes and total number of no.

SAMPLE INPUT
1
6 6
J 1 3
? 2 3
J 3 6
? 5 1
J 1 5
? 1 3
SAMPLE OUTPUT
1 2
Explanation

There are 6 team in Contest and 6 announcement made by CYPHER
J 1 3 : team 1 and team 3 now working together
? 2 3 : the answer is NO
J 3 6 : team 3 and team 6 now working together
? 5 1 :the answer is NO
J 1 5 : team 1 and team 5 now working together
? 1 3 :the answer is YES

So output is 1 2

Time Limit: 1.0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB
Marking Scheme: Marks are awarded when all the testcases pass.
Allowed Languages: C, C++, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala, Scala 2.11.8, Swift, Visual Basic

CODE EDITOR

Initializing Code Editor...
Your Rating:

Contributor

Notifications
View All Notifications