Envíos

3736 - Sistema de Autobuses para Megatown

Creado por Yonny Mondelo Hernández
Adicionado por ymondelo20 (2016-09-10)
Límites
Tiempo Total: 30000 MS | Tiempo Caso: 2000 MS |Memoria: 256 MB | Salida límite (mb): 64 MB | Tamaño: 16 KB
Lenguajes activados
Disponible en

Descripción

Megatown is a large and far away country where hundreds of millions of people live. As in many other countries of the world, the Megatown citizens have elected a government to make Megatown a better place to live: they hope the government would solve some of their problems, regulate trade, conduct foreign relations, and other complex tasks.

Next year, the government plans to introduce a new computer assisted bus system that will provide efficient and affordable transportation to its citizens. Due to its size, Megatown is divided into P different provinces, each one with its own regulation and particular needs. So, the government decided to design one bus system per province, each one independent from (and not connected to) the bus system in other provinces.

For the i-th province in Megatown, we know that the area to be covered by the bus system consists of Ni cities and Ei bidirectional roads connecting them. The cities in the i-th province are conveniently numbered from 1 to Ni. It is guaranteed that no province of Megatown has fewer than two cities or has no roads.

When designing a bus system for a province, the Megatown architects decided that it should be redundant: there should be at least two distinct bus routes between every pair of cities in the province and these two routes must share no cities in common other than the starting and ending cities and should not be repeated cities in any of the routes (in graph theoretical terms, the two routes are disjoint and both are simple). A route between two cities is a sequence of connected roads that allows their citizens to travel between the two cities. Depending on the number of roads in the province and their distribution, it may be impossible to design a redundant bus system.

Your task is to check, for every province in Megatown, whether it is possible to design a redundant bus system in that province.
Megatown es un grande y muy lejano país donde habitan cientos de millones de personas. Como en muchos otros países del mundo, los ciudadanos de Megatown han elegido un gobierno para hacer de Megatown  un mejor lugar para vivir: ellos esperan que el gobierno resuelva algunos de sus problemas, regule el comercio, conduzca las relaciones exteriores, y realice otras complejas tareas.

Para el próximo año, el gobierno pretende introducir un nuevo sistema de autobuses asistido por computadoras que proveerá a los ciudadanos de una transportación eficiente y confortable. Debido a su tamaño, Megatown está dividido en P provincias diferentes, cada una de ellas con sus propias regulaciones y necesidades. Por lo tanto, el gobierno ha decidido diseñar un sistema de autobuses por provincia, cada uno independiente de (y no conectado con) los sistemas de autobuses de las restantes provincias.

Para la iésima provincia de Megatown, conocemos que el área a ser cubierta por el sistema de autobuses consiste en Ni ciudades y Ei caminos bidireccionales que las conectan. Las ciudades en la iésima provincia están convenientemente numeradas entre 1 y Ni. Se garantiza que no habrá provincias en Megatown con menos de dos ciudades o con cero caminos.

Al diseñar el sistema de autobuses para una provincia, los arquitectos de Megatown decidieron que dicho sistema debía ser redundante: debe existir al menos dos rutas diferentes de autobuses entre cada par de ciudades en la provincia y estas dos rutas no deben tener ninguna ciudad en común excepto las ciudades de partida y destino (inicio y fin de las rutas) y no deben haber ciudades repetidas en ninguna de las rutas (en términos de teoría de grafos, las dos rutas son disjuntas y ambas son rutas simples). Una ruta entre dos ciudades es una secuencia de caminos conectados que permite a los ciudadanos viajar entre las dos ciudades. Dependiendo de la cantidad de caminos en la provincia y de su distribución, puede ser imposible diseñar un sistema de autobuses redundante.

Su tarea consiste en comprobar, para cada provincia en Megatown, si es posible o no diseñar un sistema de autobuses redundante en esa provincia.
Megatown is a large and far away country where hundreds of millions of people live. As in many other countries of the world, the Megatown citizens have elected a government to make Megatown a better place to live: they hope the government would solve some of their problems, regulate trade, conduct foreign relations, and other complex tasks.

Next year, the government plans to introduce a new computer assisted bus system that will provide efficient and affordable transportation to its citizens. Due to its size, Megatown is divided into P different provinces, each one with its own regulation and particular needs. So, the government decided to design one bus system per province, each one independent from (and not connected to) the bus system in other provinces.

For the i-th province in Megatown, we know that the area to be covered by the bus system consists of Ni cities and Ei bidirectional roads connecting them. The cities in the i-th province are conveniently numbered from 1 to Ni. It is guaranteed that no province of Megatown has fewer than two cities or has no roads.

When designing a bus system for a province, the Megatown architects decided that it should be redundant: there should be at least two distinct bus routes between every pair of cities in the province and these two routes must share no cities in common other than the starting and ending cities and should not be repeated cities in any of the routes (in graph theoretical terms, the two routes are disjoint and both are simple). A route between two cities is a sequence of connected roads that allows their citizens to travel between the two cities. Depending on the number of roads in the province and their distribution, it may be impossible to design a redundant bus system.

Your task is to check, for every province in Megatown, whether it is possible to design a redundant bus system in that province.

Especificación de entrada

The first line of input contains an integer P (1 1000) representing the number of provinces in Megatown. For each province, a set of lines with the following format will be provided:
  • A first line with two space-separated integers Ni and Ei (2  Ni 1000, 1 Ei (Ni * (Ni - 1)) / 2, 1 i P) denoting the number of cities and roads in the i-th province.
  • Then follows a set of exactly Ei lines, each one containing exactly two distinct space-separated integers between 1 and Ni : these are the IDs of two cities which belongs to the i-th province such that they are connected by a road. You can safely assume there will be at most one road between any pair of cities.
You can safely assume there are at most 105 cities and at most 106 roads in all the country of Megatown.
La primera línea de entrada contiene un número entero P (1 1000) que representa la cantidad de provincias en Megatown. Por cada provincia, un conjunto de líneas con el siguiente formato será proporcionado:
  • Una primera línea con dos números enteros Ni y Ei (2  Ni 1000, 1 Ei (Ni * (Ni - 1)) / 2, 1 i P) separados por un espacio; representan la cantidad de ciudades y caminos en la iésima provincia.
  • Luego sigue un conjunto de exactamente Ei líneas, cada una conteniendo exactamente dos números enteros diferentes entre 1 y Ni separados por un espacio: los mismos representan los identificadores de dos ciudades que pertenecen a la iésima provincia de manera tal que estas ciudades están conectadas por un camino. Usted puede asumir con seguridad que habrá a lo sumo un camino entre cualquier par de ciudades.
Usted puede asumir con seguridad que habrá a lo sumo 105 ciudades y a lo sumo 106 caminos en todo el país de Megatown.
The first line of input contains an integer P (1 1000) representing the number of provinces in Megatown. For each province, a set of lines with the following format will be provided:
  • A first line with two space-separated integers Ni and Ei (2  Ni 1000, 1 Ei (Ni * (Ni - 1)) / 2, 1 i P) denoting the number of cities and roads in the i-th province.
  • Then follows a set of exactly Ei lines, each one containing exactly two distinct space-separated integers between 1 and Ni : these are the IDs of two cities which belongs to the i-th province such that they are connected by a road. You can safely assume there will be at most one road between any pair of cities.
You can safely assume there are at most 105 cities and at most 106 roads in all the country of Megatown.

Especificación de salida

For each province you must output a line with the word "YES" if it´s possible to design a redundant bus system in that province or the word "NO" otherwise.
Por cada provincia usted debe imprimir una línea con la palabra "YES" si es posible diseñar un sistema de autobuses redundante en esa provincia o la palabra "NO" en otro caso.
The first line of input contains an integer P (1 1000) representing the number of provinces in Megatown. For each province, a set of lines with the following format will be provided:
  • A first line with two space-separated integers Ni and Ei (2  Ni 1000, 1 Ei (Ni * (Ni - 1)) / 2, 1 i P) denoting the number of cities and roads in the i-th province.
  • Then follows a set of exactly Ei lines, each one containing exactly two distinct space-separated integers between 1 and Ni : these are the IDs of two cities which belongs to the i-th province such that they are connected by a road. You can safely assume there will be at most one road between any pair of cities.
You can safely assume there are at most 105 cities and at most 106 roads in all the country of Megatown.

Ejemplo de entrada

2
5 4
1 3
2 3
3 4
3 5
5 5
1 2
2 3
3 4
4 5
1 5

Ejemplo de salida

NO
YES

Sugerencia(s)