Hello, Codeforces!

(Disclaimer: I know very little about flows and matchings)

An interesting idea that I heard at the University recently was a greedy algorithm to find the maximum matching in a bipartite graph. The idea is simple, at each step take the node with the smallest number of unmatched neighbours (I will call it active degree) and match this node with one of its neighbours. Specifficaly match it with the neighbour whose active degree is the smallest. Update the active degree for all neighbours of the 2 nodes. Repeat until you can't match anything.

Noone in class was able to find a counter example, but we also couldn't prove that it is correct (which it likely isn't).

If anyone would be kind enough to provide a counter example / proof / link to some paper / article I would be very thankful.

I was wondering if there is any faster algorithm than O(N^2) that solves the following problem: Given a tree made of N nodes, where each node has an integer value asociated to it, find the minimum/maximum distance between two nodes whose values are coprime(if such a pair exists).

For example, given the following tree:

The minimum distance is 1 and can be obtained in multiple ways, but one of them is:

And the maximum distance is 4 and can be obtained like this:

I couldn't find anything like this by googling so I thought this is the best place to ask. Thank you in advance.