Harry And Ron Got A Map | CodeChef

Harry And Ron Got A Map

Problem code: AMC3

All submissions for this problem are available.

Harry & Ron used to be good friends until they got a map of a treasure. Harry being a greedy and opportunist thought to acclaim the treasure alone. Ron came to know about his intentions and they had a fight and amidst the fight , the map got torn into pieces.

Now, since none of them would ever get to the treasure until they compromise, so both of them settled the differences in between.

Now, in order to get the treasure, they have to consolidate the pieces together, so that they get back the original map.

So help them to find the correct map.

Input

  • First line of input contains an integer A.

    •     Which denotes the number of edges in the in first graph.

  • Next A lines contains two integer 'a1', 'b1' .

    •     Which defines the bidirectional relationship in graph 'A'.

  • ( A + 2 ) th contains an intiger B .

    •     Which denotes the number of edges in the in second graph.

  • Next B lines contains two integetr 'a2', 'b2' .

    •     Which defines the bidirectional relationship in graph 'B'.

 

Output

    Output a single line containing 'YES' or 'NO'
    if both the graphs are Similar or Not respectively .

Constraints

  • 1 ≤ A + B ≤ 7*105
  • 1 ≤ a,b ≤ 103

Subtasks

Subtask #1 (50 points):

  • 1 ≤ A + B ≤ 103

Subtask #2 (50 points): original constraints

Example

Input:
5
1 2
4 3
3 2
4 5
5 3
5
3 1
1 2
4 5
4 3
3 2

Output:
NO

 

Explanation

Author: 1★chhekur
Editorial https://discuss.codechef.com/problems/AMC3
Tags chhekur, codh2018, easy, graph
Date Added: 24-01-2018
Time Limit: 1 sec
Source Limit: 50000 Bytes
Languages: C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, rust, SCALA, swift, 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, kotlin, PERL6, TEXT, SCM chicken, CLOJ, COB, FS


Comments

  • Please login at the top to post a comment.

SUCCESSFUL SUBMISSIONS


Fetching successful submissions