SOLVE

LATER

Fredo and his Birthday Gift

Problem

Editorial

Analytics

It was Fredo's birthday yesterday. He got a simple graph of $$N$$ vertices and $$M$$ edges as one of the birthday gifts. He has been bragging about his gift to all his friends. One of his friends asked him to do the following task on the graph:

For each of the vertices in the graph, find the **maximum length simple path** ending at that vertex.

Being unable to solve it himself, he asks you for help. Help Fredo!

Note: Length of a simple path= number of edges in the path.

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 for each vertex(starting from vertex 1) , length of the maximum length simple path ending at that vertex.

**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 edges connecting the vertices, so the length of maximum length simple path = 0 for each vertex.

In the second case,

Simple paths ending at vertex 1: 4-2-1, 4-3-1, 2-1, so answer = 2

Simple paths ending at vertex 2: 1-2, 3-2, 4-2, so answer = 1

Simple paths ending at vertex 3: 1-2-3, 2-3, 4-2-3, so answer = 2

Simple paths ending at vertex 4: 1-2-4, 3-2-4, 2-4, so answer = 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++,
C++14,
Clojure,
C#,
D,
Erlang,
F#,
Go,
Groovy,
Haskell,
Java,
Java 8,
JavaScript(Rhino),
JavaScript(Node.js),
Julia,
Kotlin,
Lisp,
Lisp (SBCL),
Lua,
Objective-C,
OCaml,
Octave,
Pascal,
Perl,
PHP,
Python,
Python 3,
R(RScript),
Racket,
Ruby,
Rust,
Scala,
Swift,
Visual Basic

Initializing Code Editor...

{"0bba881": "/pagelets/recommended-problems/algorithm/fredo-and-his-birthday-gift-4/", "f3b8c9c": "/pagelets/problem-author-tester/algorithm/fredo-and-his-birthday-gift-4/", "c9dcc69": "/pagelets/show-submission/algorithm/fredo-and-his-birthday-gift-4/", "0986ec2": "/pagelets/suggested-problems/algorithm/fredo-and-his-birthday-gift-4/", "7df92a5": "/pagelets/problems-hint/algorithm/fredo-and-his-birthday-gift-4/"}

realtime.hackerearth.com

80

ad3a566541af4a2f31b1bb0bad14633b4a5405ec

58a29e5cae2309f04b28

/realtime/pusher/auth/