"to belong to" means to be part of something or to be property of someone/something. "to belong with" means to match or to suit and maybe to deserve. You belong with each other - could mean you don't match each other (you are too different, or may one doesn't deserve the other).

Hello! The first one means that person A is the property of person B and vice versa. The second one is a way of saying that person A and B fit very well together.

I'd say "belong to"