这是程序员的挑战(Bears& Bees) [英] Here is the Challenge For Programmers (Bears & Bees )

问题描述

您是否曾经想过，如果在某个问题中使用无向图时，如果图的边缘实际上是其顶点而图的顶点是其边缘，则解决起来会更容易?这个问题是正确的-不幸的是，这与熊和蜜蜂无关(但是，如果您愿意，您可能会认为顶点和熊一样，而边缘也和蜜蜂一样(或者反之亦然)).

假设您得到了一个无向图G0，它具有N个顶点和M个边.让我们对图G0执行一个简单的变换，以获得具有M个顶点的图G1，使得G1的每个顶点对应于G0的唯一边，并且当且仅当对应于G1中的一对顶点通过一条边连接时， G0的边缘共享一个公共顶点.同样，让我们​​对图G1执行简单的转换以获得图G2，然后让我们对图G2执行简单的转换以获得图G3.

您要做的就是在G3中输出顶点和边的数量.

输入

输入文件的第一行包含一个整数T-测试用例的数量(不超过10个).每个测试用例由包含两个整数N和M(1≤N，M≤1000)的行描述，后跟M行，每个行包含1到N之间的两个整数(包括1和N)，由单个空格分隔并描述图的边缘G0.确保每个边缘连接两个不同的顶点，并且每对顶点最多由一个边缘直接连接.

输出

对于每个测试用例输出，只有一行包含两个整数-G3中的顶点和边的数量.

说明:

在第一个测试案例中，给定的图形是一个三角形".很容易看到，对三角形的简单转换会产生相同的三角形(因为它包含三个成对连接的顶点和三个成对连接"的边).

Have you ever thought, when given an undirected graph in some problem, that it would be easier to solve it if the graph''s edges were actually its vertices and the graph''s vertices were its edges? This problem is right about this -- unfortunately, not about bears and bees (but if you want, you may think of vertices as of bears and of edges as of bees (or even vice versa)).

Suppose you''re given an undirected graph G0 with N vertices and M edges. Let''s perform a simple transformation on graph G0 to obtain graph G1 with M vertices so that each vertex of G1 corresponds to a unique edge of G0 and a pair of vertices in G1 is connected by a single edge if and only if the corresponding edges of G0 share a common vertex. Similarly, let''s perform a simple transformation on graph G1 to obtain graph G2, and let''s perform a simple transformation on graph G2 to obtain graph G3.

All you have to do is to output the number of vertices and edges in G3.

Input

The first line of the input file contains one integer T -- the number of test cases (no more than 10). Each test case is described by a line containing two integers N and M (1 ≤ N, M ≤ 1000) followed by M lines, each containing two integers between 1 and N, inclusive, separated by a single space and describing an edge of graph G0. It''s guaranteed that each edge connects two distinct vertices and each pair of vertices is directly connected by at most one edge.

Output

For each test case output just one line containing two integers -- the number of vertices and edges in G3.

Explanation:

In the first test case the given graph is a "triangle". It''s easy to see that a simple transformation on a triangle results in the same triangle (as it contains three pairwise connected vertices and three pairwise "connected" edges).

推荐答案

我们不做您的作业:这是有原因的.在这里，您可以考虑自己被告知的内容，并尝试理解它.也可以在那里帮助您的导师识别您的弱点，并将更多的注意力放在补救措施上.

自己尝试，您可能会发现它并不像您想的那么困难！

We do not do your homework: it is set for a reason. It is there so that you think about what you have been told, and try to understand it. It is also there so that your tutor can identify areas where you are weak, and focus more attention on remedial action.

Try it yourself, you may find it is not as difficult as you think!

这篇关于这是程序员的挑战(Bears& Bees)的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！