Here are the three problem that came in ZEPTO SDE, all of them based on someway or the other standard tree/graph ideas. Some of them are recurring hacker-earth problems that pop up here and there in some random OAs. I feel like this can be a good exercise on trees.

Problem 1: Maximum candies

Given a tree of N nodes and N-1 edges rooted at node 1, with exactly one candy placed at each node. Let's say the cost of the candy placed on ith node is ai, You have K amount of money. Now, you will choose exactly one node (say, u) and will start buying the candies placed on the path from node u to the root until you run out of money, that is, first, you will buy the candy placed at node u, then the candy placed at the ancestor of u, then its ancestor and so on until you run out of money or you reach root node. Also, you cannot skip over a node without buying the candy placed at that node.

Calculate the maximum number of candies in a given amount of money you can buy by choosing exactly one starting node.

Note: A graph is connected if, for each pair of nodes u and v, there exists a path between these two nodes in the graph. A tree is a connected graph with N nodes and N - 1 edges.

Constraints: $$${1 \le N \le 10^5}$$$

Problem 2:

In the ancient kingdom of Algoria, a vast forest/spreads across the land, and the kingdom's prosperity is intertwined with the mystical tree of knowledge. This enchanted tree, known as the Algorian Tree, holds immense power and wisdom within its many nodes. Each node of the tree contains a magical value that represents a piece of the kingdom's heritage. You have been given the task of uncovering secrets hidden within the Algorian Tree. The King has issued a decree that you must answer various queries about the tree to aid in the kingdom's governance and protection. The Algorian Tree consists of N nodes ($$${1 \le N \le 2* 10^5}$$$). Each node i holds a magical value a[i] ($$${1 \le a[i] \le 10^9}$$$). The tree is connected by N-1 mystical paths (edges) that link pairs of nodes (U,V), where each path connects nodes U and V.

The King has Q queries ($$${1 \le Q \le 2 * 10^5}$$$) for you to answer. Each query is represented by three integers (U,V,w1):

U and V are nodes in the tree. w1 is a magical threshold value.

For each royal query (U,V,w1), determine how many nodes in the path from node U to node V (inclusive) have values less than or equal to w1.

Problem 3: The Quest for the Balanced Kingdom

In the ancient kingdom of Graphlandia, there exists a network of towns and roads connecting them. The kingdom is vast, with up to 500,000 towns and a complex web of roads. King Graphon, the wise ruler of Graphlandia, dreams of transforming his kingdom into a balanced and harmonious realm.

The king's chief advisor, Sir Biparte, suggests that the kingdom can achieve perfect harmony if the towns can be divided into two distinct groups such that no two towns within the same group are directly connected by a road. These groups will be named "The Azure Alliance" and "The Crimson Coalition." However, due to centuries of unplanned construction, the kingdom's road network has grown tangled and chaotic.

A King Graphon has tasked you, the kingdom's master architect, with the mission to help him realize this dream. Your goal is to analyze the existing network and determine the maximum number of roads that can be removed to achieve this balanced division of towns. Each town can only have up to two roads leading to other towns, and no town connects back to itself.

Input

The first line contains two integers n and m, where n is the number of towns ($$${1 \le N \le 5 * 10^5}$$$) and m is the number of roads ($$${1 \le m \le n}$$$).

The next m lines each contain two integers x and y ($$${1 \le x, y \le n}$$$), representing a road between town x and town y.

Output

Print a single integer, the maximum number of roads that can be removed to achieve the king's vision of a balanced kingdom.