We are given on undirected graph of N nodes and M edges, and we should paint each node in either color
one, two or three such that in the end.
I have and one node's equals one and two notes equal to two and end free notes equal to free.
And of course, I can't just color it.
However I want.
I have to make sure that for each age you M.V., the difference between the values of not you and the.
Is exactly one.
And that's it.
Good.
So let's do something nice here.
I will give you some hints and you will solve the question afterwards.
So let me think how I thought about this, right.
I mean, the contest, right.
I read the problem and I'm like, OK, and is at most five thousand.
This means at some point I'm going to do some dynamic programming in bigger event squared for sure,
because usually when you have trees or other problems, you can have like one hundred thousand nodes.
And that's cool because you just do a DFS.
But when you have five thousand, it's clearly that you need an N squared, which is a dynamic programming
probably.
So at some point I'm going to do that.
But on the right now I have free colors and and one and two in free.
And on undirected graph.
So I'm thinking like.
Hmm.
Can I solve a simple problem?
What would be a simple problem?
Well, I have an undirected graph and free Koller's.
What about a tree?
If I had a three.
And two colors.
So I thought about the simplest problem ever.
I love to do that.
I just sort of the simple problems every time, bro.
I mean, that's the way to solve the problems.
Always sort of the simple problems.
So I have a tree and I have two colors.
How do I do it?
Is it possible to color a tree in two colors with those constraints and then a stroke?
The following idea.
Well, if I have a tree and only two colors.
It's just about the route when having a tree.
If I set the color of the route, then I know the color of the whole tree.
Right.
Super simple.
I mean, you can imagine that if I had here.
One in each and every son.
I would have here to.
In each and every of these sons I would have here.
Only once.
Why?
Because I have only two colors.
So we have two colors.
Everything is super simple.
You just have two possible configurations.
The first one is when the root.
Is one and the whole subtree just colors itself.
And the second one is when the root is two and it is exactly the same thing, but reverse scholars call.
This is a treat with two colors.
What about a graph with two colors?
Same thing.
It's exactly the same thing.
If you have a graph, a graph is a tree which has at least or maybe has at least one cycle.
So you just take a random note.
As we had taken the routine, the three.
Color it with one or two.
And then, you know, the colors of its neighbors.
If this is one each and every neighbor is.
This is our to each and every of their neighbors is what?
And so on and so forth.
So.
The two color problems is that our problem is super simple.
How about a treat we free colors?
Hmm, that's a little bit more challenging.
Three with three colors.
OK.
Well, if I have solved the simple problems, of course, I'm going to take advantage of that and use
those approaches.
So has to be something about this route, right?
If I colored the route, routine one.
What is the color of its sons?
I think I know that right?
Just has to be too cool.
Now, if all of these sons are too, what are the colors of their son?
I don't know.
Could be one or free.
But what I know for sure is that each of these nodes have either color one or color free.
And I can freely choose.
Which color I want, I can take each of these nodes and for each node I can choose either one or free.
It's cool.
It's going to be correct.
Right.
And then the gold observation, the golden observation is that no matter what color, let's say this
note has either one or free its suns are again going to be all of them to.
Everybody in the next level is.
So take the route, which was one, by the way, the route could have been free.
So the first level is a one or freak level, which means each and every note is either one or three.
The next level is a two level each and every note is true.
Then the next level is, again, one or free.
And the next is again, too.
And guess what, the next will be again, one or free and so on and so forth.
So this is the first observation that I've made.
If I would have a tree, I have, again, two possible scenarios.
But they are more general.
The fourth scenario not.
Levels are full of twos, right?
This is the first scenario as simple as that.
And he even levels.
Are one or free, so.
Or.
It's everywhere, just values of two.
Means one or for.
Does the first possible scenario and the second possible scenario is the reverse?
Or is one or free?
And even means to this happens when.
Of course, I pick the route to be true.
And then each and every not here is one or free, then all the nodes are again to one or free and so
on and so forth.
So I basically have only two scenarios.
I have to think about those.
If this is a three.
What if it was a graph?
What is a graph?
A graph is a three.
That's really what the graph is.
But what?
Yeah, you know what the graph is?
A tree that has better edges.
So if I can't do this for a tree, I won't do this for a gruff.
Right, because.
For a graph, for the whole graph to satisfy those properties, this means it has a partial tree which
will also satisfy those properties.
So if I can't solve it for the partial tree of the graph, I can solve it for the whole rough.
So you should think of your Grauwe.
Because it's not connected.
You should separate each and every connected competent and you should think of each connected component
of this.
A tree with some big edges.
And because in this kind of tree, you have two possible scenario scenarios.
You just have to think, OK.
So in the first scenario, each or the level has only twos and the even once one or free, what is the
property that this bag edges should have in order for a disconnected component to be valid?
I shouldn't have a back edge between two nodes that have the same level.
Party because I have if I have a back edge between.
Who even knows?
So this this is even.
And this is even if I have a back edge between two even levels, these even levels are either both fully
values of two.
Or either both full of values of one or free.
Either case is invalid.
I can't have an edge from two to two and I have I can't have an edge from one or free to one or free.
So what has to be done here in order to make the transition from three to Grauwe?
Is to get a partial three of the graph and for each and every Beck edge, make sure.
The levels of those two nodes of the package have different party.
If this happens for each connected component, then you are fine.
But the answer is not yes.
Remember, you should have.
And one.
And two and and three and one of one's.
And two of twos and end free of threes.
And this is your home.
Think about how to satisfy the number of values.
So, again, each connected component.
They are independent of each other.
Check if it is valid.
So there is no baggage between levels of the same party.
So that's basically it.
Right.
And your homework is to think about how you should combine this and how you should for each connected
component.
Choose either first option, the order levels or the second one, the evil levels in order to combine
them together and have to have a total of one and two and every letter, guys.