SOLVE

LATER

Fredo's Crush

Problem

Editorial

Analytics

Fredo has crush on a girl in his class. He went to ask her out for a date. She, being a coder, gave her a simple graph with $$N$$ vertices and $$M$$ edges and asked him to solve a problem on the graph in order to go on a date with her.

The problem says:

Let there be some functions defined below:

For each vertex in the graph:

**S = max (sum of all vertices lying in the maximum length simple path ending at that vertex)**

That is, if there are two simple paths with length 3 ending at some vertex and there can be no simple path with length greater than 3, and P be the sum of vertices of first path and Q of second. So, S = max(P,Q).

Let **A = minimum value of S[i]** ($$1 \le i \le n$$)

**B = maximum value of S[i]** ($$1 \le i \le n$$)

You are given an equation **Ax = By**

Find the minimum value of $$x$$ and $$y$$ satisfying the equation.

Note: If there are no simple paths ending at some vertex, S for that vertex will be number of that vertex.

A simple path is a path in a graph which does not have repeating vertices.

**Input Format**:

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

First line of each test case consists of two space separated integers denoting $$N$$ and $$M$$ and the following $$M$$ lines consist of two space separated integers $$X$$ and $$Y$$ denoting there is an edge between vertices $$X$$ and $$Y$$.

**Output Format**:

For each test case, print the values of $$x$$ and $$y$$ (space separated) in a separate line.

**Constraints**:

$$ 1 \le T \le 10 $$

$$ 1 \le N \le 15 $$

$$ 0 \le M < N*(N-1)/2 $$

$$ 1 \le X, Y \le N $$

Explanation

In the first case, there are no simple paths ending at any vertex, so S={1,2,3}, we need to solve for 1 * x=3 * y.

In the second case,

paths ending at 1 are: 3-2-1 and 2-1. The maximum length path is 3-2-1 having sum=3+2+1=6

paths ending at 2 are: 1-2 and 3-2. Both have the same length, s[2]=max(1+2,3+2)=5

and similarly for 3, s[3]=6

so we need to solve for 5 * x=6 * y.

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

Initializing Code Editor...

{"2ee55f9": "/pagelets/problems-hint/algorithm/fredos-crush-2/", "2ee5616": "/pagelets/recommended-problems/algorithm/fredos-crush-2/", "2ee5539": "/pagelets/suggested-problems/algorithm/fredos-crush-2/", "2ee4a22": "/pagelets/show-submission/algorithm/fredos-crush-2/", "2ee55d8": "/pagelets/problem-author-tester/algorithm/fredos-crush-2/"}

{}

realtime.hackerearth.com

80

21dc3dd1d722d423257371eeef30effe94b3aa73

58a29e5cae2309f04b28

/realtime/pusher/auth/