DAPC24-086.Chaotic Cables

Medium · 1 s · 256 MB

icpc
dapc
2024

Your friend Claas is in charge of designing the network for the newly constructed computer lab. Aware of the critical importance of efficiency in network design, Claas opted for the sophisticated Binary Access Point Configuration (BAPC) network topology.

A network is classified as a BAPC network precisely if we can assign a binary address of a fixed length to each device within the network, ensuring that:

1. Devices are connected if and only if their addresses differ in exactly one bit.
2. Each possible address is assigned to exactly one device.

Claas started out wiring devices together, but as the intricate web of connections began to take shape, doubt crept into his mind. Was the network he painstakingly constructed truly a BAPC network?

Help Claas determine if the network is a BAPC network.

Giriş formatı

The input consists of:

• One line with two integers $n$ and $m$ ( $2 \le n \le 2\cdot 10^5$ , $1 \le m \le 2\cdot 10^5$ ) the number of devices and the number of wires in the network.

• $m$ lines with integers $a$ and $b$ ( $1 \leq a, b \leq n$ , $a \ne b$ ), indicating that there is a wire between devices $a$ and $b$ .

It is guaranteed that each pair of devices is connected by at most one wire.

Çıxış formatı

Output “yes” if the network is a BAPC network. Otherwise, output “no”.

Qeyd

Source: Delft Algorithm Programming Contest 2024 · Author: Mees de Vries · License: CC BY-SA 4.0 · Original: https://dapc.wisv.ch · Statement adapted for AlgoLens and shared under the same license. · 67 of the 187 original test cases (the largest) are omitted here to keep the problem lightweight.

Nümunələr

Giriş #1

Çıxış #1

no

Giriş #2

Çıxış #2

yes